package LeetCode;
import java.util.*;
public class LeetCodeMain12 {
    List<List<Integer>> list=new ArrayList<>();
    List<Integer> list1=new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used=new boolean[nums.length];
        Arrays.sort(nums);
        back(nums,used);
        return list;
    }
    public void back(int[] nums,boolean[] used){
        if (list1.size()== nums.length){
            list.add(new ArrayList<>(list1));
            return;
        }
        Set<Integer> set=new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])){
                continue;
            }if (used[i]==false){
                set.add(nums[i]);
                used[i]=true;
                list1.add(nums[i]);
                back(nums,used);
                used[i]=false;
                list1.remove(list1.size()-1);
            }
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        back3(candidates,target,0,0);
        return list;
    }
    public void back3(int[] candidates,int target,int startIndex,int sum){
        if (sum==target){
            list.add(new ArrayList<>(list1));
            return;
        }
        Set<Integer> set=new HashSet<>();
        for (int i = startIndex; i < candidates.length&&(sum+candidates[i]<=target); i++) {
            if (set.contains(candidates[i])){
                continue;
            }
            set.add(candidates[i]);
            list1.add(candidates[i]);
            sum+=candidates[i];
            back3(candidates,target,i+1,sum);
            sum-=candidates[i];
            list1.remove(list1.size()-1);
        }
    }
    public List<List<Integer>> permuteUnique1(int[] nums) {
        boolean[] used=new boolean[nums.length];
        Arrays.sort(nums);
        back2(nums,used);
        return list;
    }
    public void back2(int[] nums,boolean[] used){
        if (list1.size()==nums.length){
            //暴力排重
//            if (list.contains(list1)==false){
//                list.add(new ArrayList<>(list1));
//            }
            list.add(new ArrayList<>(list1));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i>0&&nums[i]==nums[i-1]&&used[i-1]==false){
                continue;
            }
            if (used[i]==false){
                used[i]=true;
                list1.add(nums[i]);
                back2(nums, used);
                used[i]=false;
                list1.remove(list1.size()-1);
            }
        }
    }
    public List<List<Integer>> findSubsequences(int[] nums) {
        back1(nums,0);
        return list;
    }
    public void back1(int[] nums,int startIndex){
        if (list1.size()>1){
            list.add(new ArrayList<>(list1));
        }
        int[] num=new int[201];
        for (int i = startIndex; i < nums.length; i++) {
            if ((!list1.isEmpty()&&nums[i]<list1.get(list1.size()-1))||num[nums[i]+100]==1){
                continue;
            }
            num[nums[i]+100]=1;
            list1.add(nums[i]);
            back1(nums,i+1);
            list1.remove(list1.size()-1);
        }
    }
}
